//分两种情况：
// 1：最大数组和在中间，和平时一样解法
// 2：最大数组和是跨越头尾，则说明从两边出发往中间靠拢必须都是最大，那就说明中间段就是最小，问题转变为求最小数组
import java.util.Arrays;

public class Solution918 {
    public int maxSubarraySumCircular(int[] nums) {
        int[] f=new int[nums.length];
        f[0]=nums[0];
        int ans=f[0];
        for (int i=1;i<nums.length;i++){
            if (f[i-1]<=0){
                f[i]=nums[i];
            }else{
                f[i]=nums[i]+f[i-1];
            }
            ans=Math.max(ans,f[i]);
        }
        f[0]=nums[0];
        int ans2=f[0];
        for (int i=1;i<nums.length;i++){
            if (f[i-1]>=0){
                f[i]=nums[i];
            }else{
                f[i]=nums[i]+f[i-1];
            }
            ans2=Math.min(ans2,f[i]);
        }
        if (Arrays.stream(nums).sum()==ans2){
            return ans;
        }
        return Math.max(ans, Arrays.stream(nums).sum()-ans2);
    }

    public static void main(String[] args) {
        System.out.println(new Solution918().maxSubarraySumCircular(new int[]{5,-3,5}));
    }
}
